package com.gaogzhen.algorithm.sort;

public class Radix {
    public static int maxLength(int[] a) {
        int max = a[0];
        int len = a.length;
        for (int i = 1; i < len; i++) {
            if (a[i] > max) {
                max = a[i];
            }
        }
        int c = 0;
        while (max != 0) {
            max /= 10;
            c++;
        }
        return c;
    }

    public static void  sort(int[] a) {
        int len = a.length;
        // 1、去最大数的位数
        int maxLength = maxLength(a);

        // 2、初始化容器
        // 初始化桶
        int[][] bucket = new int[10][len];
        // 初始化桶计数
        int[] bucketCount = new int[10];
        int digit, index;
        // 排序趟数为maxLength
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            // 遍历数组，分次取个位数、十位数、...

            for (int j = 0; j < len; j++) {
                // 根据数对应的桶的位置放入桶中
                digit =  a[j] / n % 10;
                bucket[digit][bucketCount[digit]] = a[j];
                bucketCount[digit]++;
            }
            // 吧桶中数取出放回原数组
            index = 0;
            for (int k = 0; k < 10; k++) {
                if (bucketCount[k] != 0) {
                    for (int l = 0; l < bucketCount[k]; l++) {
                        a[index++] = bucket[k][l];
                    }
                    // 桶计数清零
                    bucketCount[k] = 0;
                }

            }
        }
    }
}
